Multi-field matching (MFM) involves finding in a data structure, such as a table, a match for a search target having more than one field. Typically, the data structure includes one or more entries having n-fields. The n-fields of the search target correspond to the n-fields of the entries in the data structure. A search is executed to find an entry that matches the search target, where a match occurs if the values in each of the n fields of the entry match the values in each of the corresponding n fields of the search target.
Each field in the search target typically has a fixed value, such as an integer or range of integers, while each field in an entry may have either a fixed value, such as an integer or a range of integers, or a wildcard value. A wildcard value, or simply wildcard, represents all fixed values that could be included in a field. A wildcard, also commonly referred to as a “don't care,” may be represented in the entry by, e.g., an asterisk (*). Thus, any field in an entry that has an asterisk indicates that the field matches the corresponding field of a given search target, regardless of the fixed value in the corresponding field of the search target.
For example, MFM may be used in a data-networking environment, to provide e.g., filtering, as a data packet (also simply referred to as a packet) is transmitted across a network. With filtering, a packet that arrives at a network device, e.g., a router, may be dropped if the multiple fields in its header match the corresponding multiple fields of an entry in a table on the network device. For example, one field in an entry, such as the source address field, which indicates the network address of the device from which the packet originated, may have fixed value, i.e., the device address, while the other fields in the entry have a wildcard value. In that case, any packet whose source address matches the source address of the entry, will match the entry, because the other fields in the entry, which contain wildcards, will match any values in the other corresponding fields of the packet. This is useful if, for example, the source address of a hacker system is known, so that the network device drops any packet having that source address, regardless of the values in the other fields of the packet, to prevent the hacker system from damaging the network.
One technique for performing a MFM search is a sequential search, in which each of the values in each of the n fields of a given target is compared with each of the values in each of the corresponding n fields of each entry. Because wildcards can cause more than one entry to match the target, the entries are sorted from best to worst in terms of the number of memory accesses, so that the first matching rule is the best match based on memory accesses as compared to other possible matches. However, a disadvantage of the sequential search is that the possible number of comparisons needed to find a matching entry increases with the number of entries, as does the amount of time needed to find the matching entry, if one exists.
A technique for performing a MFM search that reduces the number of comparisons is commonly known as cross-producting. In general, cross-producting involves expanding each entry that has a wildcard into multiple entries, each of which has the wildcard replaced with one of the possible fixed values the wildcard could have. Rather than comparing the target to each entry as in a sequential search, an exact-match search is executed by directly identifying the entry whose n fields match all corresponding n fields of the target. Accordingly, cross-producting reduces the number of searches as compared to a sequential search, thereby reducing the time to perform the search. However, cross-producting increases the amount of memory needed to store the data structure, because of the additional memory needed to store the expansions of entries that contain wildcards.